/*
 * @lc app=leetcode.cn id=862 lang=javascript
 *
 * [862] 和至少为 K 的最短子数组
 */

// @lc code=start
/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var shortestSubarray = function (nums, k) {
  const sums = [0];
  const q = [];
  for (let i = 0; i < nums.length; i++) sums[i + 1] = sums[i] + nums[i];

  let ret = nums.length + 1; // 给个最大值

  // q维护sums最小值
  for (let i = 0; i < sums.length; i++) {
    while (q.length && sums[i] < sums[q[q.length - 1]]) q.pop();

    while (q.length && (sums[i] - sums[q[0]] >= k)) { // 窗口尾部减去窗口中最小值
      ret = Math.min(ret, i - q[0]);
      q.shift();
    }
    q.push(i);

  }
  return ret < nums.length + 1 ? ret : -1;

};
// @lc code=end

